Logic Puzzles vs. Prisoner’s Dilemma
Also courtesy of Steamboat Steven. That guy has all kinds of neat puzzles!
There are n prisoners on a train being taken to a prison. Once they arrive there, they will each be put in separate sensory deprivation chambers. They will have no conception of how long they have been in there. However, sometimes a guard will take one of them into a room with two switches on the wall, make the prisoner flip one of the switches, and send him back to his sensory deprivation chamber. If you wait long enough, every prisoner will go to the switch room an arbitrarily large number of times (i.e., none of them will be “starved” of visits to the switch room). At any time, any prisoner may make the claim that all prisoners have been in the switch room at least once. If he is right when making this claim, they will all be set free. If he is wrong, they will all be killed.
The prisoners can discuss and agree on a strategy for the switches right now, but once they reach the prison they won’t see each other again. They don’t know the initial configuration of the switches. No prisoner will know how many other prisoners have visited the switch room before him; the person who goes to the switch room first won’t know he’s the first. They won’t know how often the guards take people to the switch room, and even if they did they wouldn’t know how much time has passed between their own visits.
How can they be guaranteed to eventually go free?
1) You need to guarantee that the guards do not muck with the switches.
2) I challenge your use of the word ‘periodically’. Well, maybe I challenge American. Stupid language.
3) Here we get into all kinds of confusing questions. Is the prison never going to get more people? Is no one going to die within the timespan of the experiment? If no one’s going to die, then there’s really no point at all of even running it — the prisoners live iff they come up with this solution on the train. So when they get off, if they figured it out then let them go. And finally, blah.
You’re thinking too literally here. This is intended to be a logic puzzle; it is encapsulated in a prison story because describing it as bit manipulations in an abstract system is boring. If I didn’t describe something, it’s probably not going to happen. The guards won’t maliciously change the switches. It will be possible to go free before anyone dies, goes insane, or decides to kill everyone. The only prisoners that will ever interact with the switch room are the ones currently on the train. There will not be any noteworthy earthquakes, floods, or alien invasions. Prisoners will not be able to dig a tunnel through the wall with a rusty spoon. No one will be waterboarded.
Your second point is a good one (nothing is happening over a regular periods), and I have edited the entry to remove that word.
I agree with your blah, but they cannot actually count switch flips. A prisoner can’t distinguish between more than 4 different situations (since there are only 2 bits of state in the switch room). However, each prisoner can count how many times he personally has been in the switch room, as well as the configuration of the switches and the action he took during each of his visits.
I don’t pretend to have the answer to this, but here are my thoughts:
I feel like trying to get every person to understand signals sent by every other person is too much to ask. So each prisoner really only has to communicate with 2 other prisoners. If prisoner 1 communicates with 2 who communicates with 3 and so on (numbers agreed upon on the train), then when person ‘n’ gets the message from n-1 she knows that everyone has been in the room before. That is, when a person enters the room if there is a signal from the previously numbered person that they have been there, then they know that all numbers before them have gone and they can signal to the next prisoner. The issue then becomes what sort of signal is unique enough to avoid confusion.
Assuming that the switches have only 2 positions (they can’t be jammed between up and down), then using binary there are only 4 possible things that can be represented by the switches. Which means to me that if there are more than 5 prisoners this will not work (also the unknown initial configuration of the switches is a problem).
Perhaps each prisoner could make a mark somehow on the wall around the switch using their teeth or claws.
Or the prisoners could just exist in prison and not risk being killed.
Or bribe the guards?
Solution (I believe)
1) People who challenge a language (whatever that means) shouldn’t include typos and grammatically errors inside of said challenge. It just looks silly.
2) You elect one prisoner to count visits. You can call him Big X.
3) Only Big X can set a switch to the off position. Big X only starts counting after he has made certain the switch is in the off position.
4) A prisoner will only flip a switch on if said switch is off. He will flip it off at most 2 times.
5) When Big X flips it off ((N-1)*2)-1 times he will demand that you let my people go.
6) You can probably optimize this with the second switch.
Re: Solution (I believe)
People who challenge a language… shouldn’t include typos and grammatically errors inside of said challenge. It just looks silly.
I tip my proverbial cup to you, sir. The most ironic part of this is that dhalps did not make any typos or grammatical errors in that comment.
You’re definitely on the right track, and pretty close to the solution! The only thing I think you’re forgetting is that a prisoner must flip a switch when he goes to the room. What should he do if both switches are already on (and what should Big X do if both switches are already off)?
Solution
Just stumbled over this web page…
Select one of the ‘n’ prisoners as the leader. This fellow is going to count the number of people who have visited the room till now. Call him ‘A’. Now, call the 2 switches ‘s1’ and ‘s2’.
Initialization:
‘A’ will start counting ONLY after his first visit to the room. At which point of time, he’s going to reset ‘s1’.
Iteration:
If the prisoner is not ‘A’, then flip ‘s1’ only if it had been turned-off, Else, flip ‘s2’.
If the prisoner is ‘A’, then flip ‘s1’ only if it had been turned-on and increment the number of visits by one, Else, flip ‘s2’.
Termination:
The whole process terminates when ‘A’ counts ‘n – 1’. (Because, he knows that he has already visited the room!)
Re: Solution
Yup, well done!